package leetcode.editor.cn.dsa22_segmentTree;
//给定一个整数数组 nums，求出数组从索引 i 到 j (i ≤ j) 范围内元素的总和，包含 i, j 两点。
// update(i, val) 函数可以通过将下标为 i 的数值更新为 val，从而对数列进行修改。
//
// 示例: 
// Given nums = [1, 3, 5]
//sumRange(0, 2) -> 9
//update(1, 2)
//sumRange(0, 2) -> 8
// 
// 说明:
// 数组仅可以在 update 函数下进行修改。
// 你可以假设 update 函数与 sumRange 函数的调用次数是均匀分布的。 
// 
// Related Topics 树状数组 线段树 
// 👍 212 👎 0

public class RangeSumQueryMutable307 {
    public static void main(String[] args) {
        int[] nums = {1,3,5};
        NumArray numArray = new RangeSumQueryMutable307().new NumArray(nums);
        System.out.println(numArray.sumRange(0, 2)); //9
        numArray.update(1, 2);
        System.out.println(numArray.sumRange(0, 2)); //8
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class NumArray {
        class SegmentTree {
            int[] value, nums;
            int n;
            SegmentTree(int[] nums) {
                this.n = nums.length;
                this.nums = nums;
                value = new int[4 * n];
                build(1, 0, n - 1);
            }
            void build(int pos, int l, int r) {
                if (l == r) {
                    value[pos] = nums[l];
                    return;
                }
                int mid = (l + r) / 2;
                int leftIndex = pos * 2;
                int rightIndex = pos * 2 + 1;
                build(leftIndex, l, mid);
                build(rightIndex, mid + 1, r);
                value[pos] = value[leftIndex] + value[rightIndex];
            }
            int query(int pos, int l, int r, int ql, int qr) {
                if (ql > r || qr < l) return 0;
                if (l >= ql && r <= qr) return value[pos];
                int mid = (l + r) / 2;
                int leftIndex = pos * 2;
                int rightIndex = pos * 2 + 1;
                int leftSum = query(leftIndex, l, mid, ql, qr);
                int rightSum = query(rightIndex, mid + 1, r, ql, qr);
                return leftSum + rightSum;
            }
            void update(int pos, int l, int r, int idx, int val) {
                if (l == r) {
                    value[pos] = val;
                    return;
                }
                int mid = (l + r) / 2;
                int leftIndex = pos * 2;
                int rightIndex = pos * 2 + 1;
                if (idx <= mid) {
                    update(leftIndex, l, mid, idx, val);
                } else {
                    update(rightIndex, mid + 1, r, idx, val);
                }
                value[pos] = value[leftIndex] + value[rightIndex];
            }
        }
        private SegmentTree segTree;
        public NumArray(int[] nums) {
            if(nums == null || nums.length == 0) return;
            segTree = new SegmentTree(nums);
        }

        public void update(int i, int val) {
            segTree.update(1, 0, segTree.n - 1, i, val);
        }

        public int sumRange(int i, int j) {
            return segTree.query(1, 0, segTree.n - 1, i, j);
        }
    }

    /**
     * Your NumArray object will be instantiated and called as such:
     * NumArray obj = new NumArray(nums);
     * obj.update(i,val);
     * int param_2 = obj.sumRange(i,j);
     */
    //leetcode submit region end(Prohibit modification and deletion)
}